package foundation.图论.最短路;


import java.util.Scanner;

/**
 * {@code Floyd} 算法
 * <p>
 * 用于计算图中任意两点之间的最短距离
 * <p>
 * <p><strong>可以有负边</strong><p/>
 * <p><strong>不能有负环</strong><p/>
 * 算法特性：
 * <ul>
 *     <li>时间复杂度：{@code O(n³)}</li>
 *     <li>空间复杂度：{@code O(n²)}</li>
 *     <li>常数时间小，容易实现</li>
 * </ul>
 * <p>
 * 适用范围：
 * <ul>
 *     <li>适用于任何图，不管有向无向、不管边权正负</li>
 *     <li>但是不能有负环（保证最短路存在）</li>
 * </ul>
 * <p>
 * 过程简述：
 * <ol>
 *     <li>{@code distance[i][j]} 表示 {@code i} 和 {@code j} 之间的最短距离</li>
 *     <li>通过动态规划更新最短路径：
 *         <pre>{@code distance[i][j] = min(distance[i][j], distance[i][k] + distance[k][j])}</pre>
 *     </li>
 *     <li>枚举所有的 {@code k} 即可完成计算</li>
 * </ol>
 */
public class Floyd {
    static int MAXN = 1001;
    static int[][] dist = new int[MAXN][MAXN];
    static int n = 1001, m = 10001;
    static int INF = Integer.MAX_VALUE;


    public static void floyd() {
        for (int k = 0; k < n; k++) {
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < n; j++) {
                    // i -> bridge -> j
                    // dist[i][j] 能否缩短
                    //dist[i][j] = min( dist[i][j] , dist[i][bridge] + dist[bridge][j] )
                    if (dist[i][k] != INF
                            && dist[k][j] != INF
                            && dist[i][j] > dist[i][k] + dist[k][j]) {
                        dist[i][j] = dist[i][k] + dist[k][j];
                    }
                }
            }
        }
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        m = sc.nextInt();
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (i == j) dist[i][j] = 0;
                else dist[i][j] = INF;
            }
        }
        for (int i = 0; i < m; i++) {
            int u = sc.nextInt();
            int v = sc.nextInt();
            int w = sc.nextInt();
            dist[u][v] = w;
            dist[v][u] = w;
        }
        floyd();
        System.out.println(dist[1][n]);
    }

}
